1873H - Mad City - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pb_ds;
#define pb push_back
#define Y cout << "YES" << endl;
#define N cout << "NO" << endl;
#define ll long long
#define mod 1000000007

vector<ll> graph[200005];
int vis[200005];
vector<ll> pa(200005, 0);

vector<ll> cyc(200005, 0);
bool check = false;

void dfs(ll v, ll par)
{

    if (check)
    {
        return;
    }

    vis[v] = true;
    for (auto u : graph[v])
    {
        if (check)
        {
            return;
        }
        if (!vis[u])
        {

            pa[u] = v;
            dfs(u, v);
        }
        else if (u != par)
        {
            check = true;
            ll node = v;

            while (node != u)
            {
                cyc[node] = 0;
                node = pa[node];
            }
            cyc[u] = 0;

            return;
        }
    }

    if (check)
    {
        return;
    }
}

ll cnt = 0;

ll mx = INT_MAX;

ll nd = -1;

void dfs1(ll v)
{
    vis[v] = true;

    for (auto u : graph[v])
    {
        if (!vis[u])
        {
            cnt++;

            if (cyc[u] == 0)
            {

                if (mx > cnt)
                {
                    mx = cnt;
                    nd = u; // is node pe entry marega
                }
            }
            dfs1(u);
            cnt--;
        }
    }
}
void solve()
{
    ll n, a, b;
    cin >> n >> a >> b;
    a--;
    b--;
    check = false;
    
    for (ll i = 0; i < n; i++)
    {
        graph[i].clear();
        vis[i] = false;
        cyc[i] = INT_MAX;
    }

    for (ll i = 0; i < n; i++)
    {
        ll u, v;
        cin >> u >> v;
        u--;
        v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    dfs(0, -1);

    // for(ll i=0;i<n;i++){
    // cout<<cyc[i]<<" ";
    // }
    // cout<<endl;
    if (a == b)
    {
        N return;
    }
    // agar pehle se cycle mein ho loda kuch nahi hoga
    if (cyc[b] == 0)
    {
        Y return;
    }
    // wo jaldi pahuchna chahta hai cycle ke andar
    mx = INT_MAX;
    nd = -1;
    cnt = 0;
    memset(vis, false, sizeof(vis));

    dfs1(b);

    memset(vis, false, sizeof(vis));

    queue<ll> q;
    q.push(a);
    vector<ll> dis(n, -1);
    dis[a] = 0;
    while (!q.empty())
    {
        ll node = q.front();
        q.pop();
        for (auto u : graph[node])
        {
            if (dis[u] == -1)
            {
                q.push(u);
                dis[u] = dis[node] + 1;
            }
        }
    }

    ll ds = dis[nd];

    if (ds > mx)
    {
        Y return;
    }
    N
}
int main()
{
    ll test;
    cin >> test;
    while (test--)
    {
        solve();
    }
    return 0;
}